package a_sorting_basic.c_insertion_sort;

import a_sorting_basic.c_insertion_sort.sorting_helper.SortingTestC;
import utils.ArrayGeneric;

/**
 * 1 选择排序  O=N^2 位置稳定 比选择排序效率略好 最好情况 只需比较不用交换
 * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
 * O（n2）	    O（n2）	    O（1）	    不是
 * 每次遍历一次数组找到一个最小值的下标， 遍历结束将第一个下标0和最小值下标的元素互换， 此时第一个元素就是排序好的
 * 外层循环次数： 数组长度 每次找到一个最小值
 * 内层循环次数： 数组长度减一 从第二个元素和第一个元素比较开始
 * 第二次遍历数组时从第二个元素开始， 找到最小值时记住下标， 遍历结束后交换两个元素， 此时前两个元素就是排序好的
 * 第三次 。。。
 * 最后一次排序检查最后一个元素
 *
 * 排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。
 */
public class SelectionSortC extends SortingTestC {

    @Override
    public void sort(ArrayGeneric arr) {
        int len = arr.length();
        for (int i = 0; i < len; i++) {
            int minIndex = i;
            for (int j = i + 1; j < len; j++) {
                // find min index for current loop
                if (arr.get(j).compareTo(arr.get(minIndex)) < 0) {
                    minIndex = j;
                }
            }
            arr.swap(i, minIndex);
        }
    }
}
